﻿public class Solution {
    public int MinDistance(string word1, string word2)
    {
        int[,] dp = new int[word1.Length + 1, word2.Length + 1];
        // 初始化
        // 递推公式
        for (int i = 0; i <= word1.Length; i++)
        {
            for (int j = 0; j <= word2.Length; j++)
            {
                if (i == 0)
                {
                    dp[i, j] = j;
                }
                else if (j == 0)
                {
                    dp[i, j] = i;
                }
                else if (word1[i - 1] == word2[j - 1])
                {
                    dp[i, j] = dp[i - 1, j - 1];
                }
                else
                {
                    dp[i, j] = new[] {dp[i - 1, j] + 1, dp[i, j - 1] + 1, dp[i - 1, j - 1] + 1}.Min();
                }
            }
        }

        return dp[word1.Length, word2.Length];
    }

    public static void Main(string[] args)
    {
        string word1 = "intention", word2 = "execution";
        Solution solution = new Solution();
        int res = solution.MinDistance(word1, word2);
        Console.WriteLine(res);
    }
}